package com.zhaopin.theswordreferstooffer;

import java.util.Objects;

/**
 * @author yin.peide
 * @date 2021-06-16 17:13
 * 面试题27： 二叉搜索树与双向链表
 * 感觉属于较难级别
 */
public class Offer27 {
    TreeNode head = null;
    TreeNode end = null;

    public static void main(String[] args) {

        //初始化一棵二叉树
//        TreeNode treeNode4 = new TreeNode(4);
//        TreeNode treeNode8 = new TreeNode(8);
//        TreeNode treeNode12 = new TreeNode(12);
//        TreeNode treeNode16 = new TreeNode(16);

        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode14 = new TreeNode(14);
        TreeNode treeNode10 = new TreeNode(10);

//        treeNode6.setLeft(treeNode4);
//        treeNode6.setRight(treeNode8);
//
//        treeNode14.setLeft(treeNode12);
//        treeNode14.setRight(treeNode16);
        treeNode10.init(treeNode6, treeNode14);

        middleOrder(treeNode10);

        System.out.println();

        Offer27 offer27 = new Offer27();
        TreeNode treeNode = offer27.convert(treeNode10);
        System.out.println();
    }

    public static void middleOrder(TreeNode treeNodeRoot) {
        if (Objects.isNull(treeNodeRoot)) {
            return;
        }
        middleOrder(treeNodeRoot.getLeft());
        System.out.print(treeNodeRoot.getValue() + " ");
        middleOrder(treeNodeRoot.getRight());
    }

    //尽量再生成每个元素的时候就设置好链表的结构
    public TreeNode convert(TreeNode treeNodeRoot) {
        convertSub(treeNodeRoot);
        return head;
    }

    public void convertSub(TreeNode treeNodeRoot) {
        if (treeNodeRoot == null) {
            return;
        }
        convert(treeNodeRoot.getLeft());
        if (end == null) {
            head = treeNodeRoot;
            end = treeNodeRoot;
        } else {
            end.setRight(treeNodeRoot);
            treeNodeRoot.setLeft(end);
            end = treeNodeRoot;
        }
        convert(treeNodeRoot.getRight());
    }
}
